/*
 * @Author: Aro
 * @Date: 2021-10-09 14:24:44
 */

// 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
// 请必须使用时间复杂度为 O(log n) 的算法。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
  var len = nums.length;
  if (nums[len - 1] < target) {
    return len;
  }
  var left = 0;
  var right = len - 1;

  // 不断改变区间
  while(left < right) {
    var middle = left + Math.floor((right - left) / 2);
    if (nums[middle] < target) {
      left = middle + 1;
    } else {
      right = middle;
    }
  }

  return left;

};

console.log("====== start ======");

var test1 = searchInsert([1, 3, 5, 6], 5);
console.log('test1的值为:' + test1);

console.log("====== end ======");

// 1 3 6 8 11
// 1 3